package com.yangli.leecode.mashib.interview;

import java.util.HashMap;

/**
 * @Description
 * @Author liyang
 * @Date 2023/2/10 16:03
 */
public class Twenty {
    public static void main(String[] args){
        Twenty twenty = new Twenty();

        System.out.println(twenty.solution("0^0|0|0&1&0&1|0^0^1|0|1^1", true));
    }

    static class Info {
        public int t;
        public int f;

        public Info(int t, int f){
            this.t = t;
            this.f = f;
        }
    }

    public int solution(String arr, boolean tag){
        if (arr.length() == 1) {
            return arr.charAt(0) == (tag ? '1' : '0') ? 1 : 0;
        }
        HashMap <String,Info> cache = new HashMap<>();
        Info info = process(arr, 0, arr.length() - 1);
        return tag ? info.t : info.f;
    }

    //要使用记忆化搜索保存数值，减少递归==>动态递归
    public Info process(String arr, int l, int r){//=只返回了tag的可能性，计算可会设计!tag可能性所以要处理下
        if (l == r) {
            int t = arr.charAt(l) == '1' ? 1 : 0;
            int f = t == 1 ? 0 : 1;
            return new Info(t, f);
        }
        int t = 0, f = 0;
        for (int i = l + 1; i < r; i += 2) { //for (int i = 0, j = (r - l) >> 1; i < j; i++) {  int temp = l + 1 + (2 * i);
            Info left = process(arr, l, i - 1);
            Info right = process(arr, i + 1, r);
            if (arr.charAt(i) == '&') {
                t += left.t * right.t;
                f += left.t * right.f;
                f += left.f * right.t;
                f += left.f * right.f;
            }
            if (arr.charAt(i) == '|') {
                t += left.t * right.t;
                t += left.t * right.f;
                t += left.f * right.t;
                f += left.f * right.f;
            }
            if (arr.charAt(i) == '^') {
                f += left.t * right.t;
                t += left.t * right.f;
                t += left.f * right.t;
                f += left.f * right.f;
            }
        }
        return new Info(t, f);
    }
}
